package dp

// https://leetcode-cn.com/problems/house-robber-ii/
// 打家劫舍 II 最后一位和第一位是连着的，不能同时抢
// 算法: 动态规划，分两种队列来算，分别算 [0, n-1] 和 [1, n] 算两次最大值
// 计算公式相同: f[n] = max(f[n-1], f[n-2] + num[n])
// 时间复杂度: O(n)
// func maxInt(a, b int) int {
// 	if a > b {
// 		return a
// 	}
// 	return b
// }

func Rob2(nums []int) int {
	if 0 == len(nums) {
		return 0
	} else if 1 == len(nums) {
		return nums[0]
	} else if 2 == len(nums) {
		return maxInt(nums[0], nums[1])
	}
	nums1 := nums[0 : len(nums)-1]
	nums2 := nums[1:]

	numsArr := [][]int{nums1, nums2}

	maxRob := make([]int, len(nums1))
	maxRet := 0
	for _, currentNums := range numsArr {
		maxRob[0] = currentNums[0]
		maxRob[1] = maxInt(currentNums[0], currentNums[1])
		for index := 2; index < len(currentNums); index++ {
			maxRob[index] = maxInt(maxRob[index-1], maxRob[index-2]+currentNums[index])
		}

		maxRet = maxInt(maxRet, maxRob[len(currentNums)-1])
	}

	return maxRet
}
